package leetcode_day._2021._202106._2130;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/24 13:31
 * 直线上最多的点数
 * 算法：数学  哈希表
 * 枚举：
 * 由三个点可以确定一条直线
 * 比较每两个点的斜率是否相等即可
 * y, x, p
 * (y[1] - x[1]) / (y[0] - x[0]) = (p[1] - y[1]) / (p[0] - y[0])
 * 哈希表
 * 可以看成从一个点出发的直线中，经过最多点的直线
 */
public class _24_149 {

    public int maxPoints(int[][] points) {
        int ans = 1;
        int len = points.length;
        for (int i = 0; i < len; i++) {
            int[] y = points[i];
            for (int j = i + 1; j < len; j++) {
                int[] x = points[j];
                int cnt = 2;
                for (int k = j + 1; k < len; k++) {
                    int[] p = points[k];
                    int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                    int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                    if (s1 == s2) ++cnt;
                }
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }

    public int maxPoints_perfect(int[][] points) {
        int ans = 1;
        int len = points.length;
        for (int i = 0; i < len; i++) {
            Map<String, Integer> map = new HashMap<>();
            int max = 0;
            for (int j = i + 1; j < len; j++) {
                int a = points[i][1] - points[j][1], b = points[i][0] - points[j][0];
                int k = gcb(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }
    // 找最大公约数，就是 a，b 都能除尽这个数，并且没有小数
    int gcb(int a, int b) {
        return b == 0 ? a : gcb(b, a % b);
    }

}
